//
// Created by liushuai on 12/19/19.
//
#include <unordered_map>
std::unordered_map<int,long> cache;
long fib(int n){
    if(cache.count(n)){
        return cache.at(n);
    }
    int result;
    if(n<2)
        result = n;
    else
        result = fib(n-1)+fib(n-2);
    cache[n] = result;
    return result;
}
